class Solution {
public:
    int minCut(string s) {
        int n = s.size();
        vector<vector<char>> dp(n, vector<char>(n));

        for (int j = 0; j < n; j++)
        {
            for (int i = j; i >= 0; i--)
            {
                if (i == j)
                    dp[i][j] = 1;
                else
                {
                    if (s[i] == s[j] && (j - i == 1 || dp[i + 1][j - 1] == 1))
                        dp[i][j] = 1;
                }
            }
        }

        vector<int> min_cnt(n, INT_MAX);    //min_cnt[i]表示0~i字串的最小分割数
        /*
            如果0~i就是一个回文串，那么最小分割数就是0
            其余情况和《单词拆分》类似，假设j ~ i为最后一次切割
                a.假设子串[j, i]是一个回文串，那么0~i的最小分割数就是min_cnt[j - 1] + 1
                b.假设子串[j, i]不是一个回文串，那么就考虑j的另外取值
            最后取0~i的最小分割数即可
        */

        min_cnt[0] = 0;
        for (int i = 0; i < n; i++)
        {
            for (int j = i; j >= 0; j--)
            {
                if (dp[0][i] == 1)
                    min_cnt[i] = 0;
                else if (dp[j][i] == 1)
                    min_cnt[i] = min(min_cnt[i], min_cnt[j - 1] + 1);
                else
                    continue; 
            }
        }
        
        return min_cnt[n - 1];
    }
};